package single_linked_list_with_head;

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList();
        list.addIndex(0, 1);
        list.addIndex(1, 2);
        list.addIndex(2, 3);
        list.addIndex(1, 6);
        list.addIndex(4, 6);
        System.out.println(list);
//        list.modifyValue(0, 6);
//        list.modifyValue(4, 1);
//        System.out.println(list);
//        list.removeNodeIndex(4);
//        list.removeNodeIndex(1);
//        list.removeNodeIndex(2);
//        System.out.println(list);
//        list.removeValueOnce(6);
//        list.removeValueAll(6);
//        System.out.println(list);
    }
}

class LinkedList<T> {
    int size;
    Node dummyNode = new Node(-1); // 给虚拟头结点设置一个无效值

    /**
     * 在有虚拟头结点的单链表的任意索引位置添加节点
     * @param index
     * @param value
     */
    public void addIndex(int index, T value) {
        Node node = new Node(value);
        // 判断合法性
        if (index < 0 || index > size) {
            System.out.println("addIndex index is illegal!");
            return;
        }
        // 因为此链表中引入了虚拟头结点，元素插入在链表的任何位置都想当在中间插入
        Node prev = dummyNode; // 这里可以保证头结点不为空，不会引发空指针错误
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    /**
     * 用于判断修改和删除单链表节点时，索引的合法性
     * @param index
     * @return
     */
    private boolean isIllegal(int index) {
        if (index < 0 || index >= size) {
            System.out.println("Index is illegal!");
            return false;
        }
        return true;
    }

    /**
     * 用于修改任意索引处的值，并返回旧值
     * @param index
     * @param newValue
     * @return
     */
    public T modifyValue(int index, T newValue) {
        if (isIllegal(index)) {
            Node<T> cur = dummyNode.next;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            T tmp = cur.value;
            cur.value = newValue;
            return tmp;
        }
        return null;
    }

    /**
     * 用于删除任意索引处的节点
     * @param index
     */
    public void removeNodeIndex(int index) {
        if (isIllegal(index)) {
            Node prev = dummyNode;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            Node tmp = prev.next;
            prev.next = prev.next.next;
            tmp.next = null;
            size --;
        }
    }

    /**
     * 用于删除这个值第一次出现所对应的节点
     * @param value
     */
    public void removeValueOnce(T value) {
        Node prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.value == value) {
                Node tmpNode = prev.next;
                prev.next = prev.next.next;
                tmpNode.next = null;
                size --;
                return;
            }
            prev = prev.next;
        }
    }

    /**
     * 用于删除这个值相等的所对应的节点
     * @param value
     */
    public void removeValueAll(T value) {
        Node prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.value == value) {
                Node tmpNode = prev.next;
                prev.next = prev.next.next;
                tmpNode.next = null;
                size --;
            } else {
                prev = prev.next;
            }
        }
    }

    public String toString() {
        Node tmpNode = dummyNode;
        String str = "";
        while (tmpNode.next != null) {
            str += tmpNode.next.value + "->";
            tmpNode = tmpNode.next;
        }
        str += "NULL";
        return str;
    }
}

class Node<T> {
    T value;
    Node next;

    public Node(T value) {
        this.value = value;
    }
}
